package com.shixianjun;

import com.shixianjun.sort.Sortable;
import com.shixianjun.sort.SortableElement;
import com.shixianjun.tools.Tools;

public class 选择排序 implements Sortable {
    public static void main(String[] args) {
        SortableElement[] arr = SortableElement.randomSortableElementArray(10, 30, true);
        SortableElement.printSortableElementArray("排序前arr", arr);
        new 选择排序().sort(arr);
        SortableElement.printSortableElementArray("排序后arr", arr);
    }
    public void sort(SortableElement[] arr) {
        sort2(arr);
    }

    /**
     * 选择排序
     * 时间复杂度：O(n)
     * 空间负责度：O(1)
     * 稳定性：不稳定
     * */
    public void sort1(SortableElement[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                minIndex = arr[j].value < arr[minIndex].value ? j : minIndex;
            }
            Tools.swap(arr, i, minIndex);
        }
    }

    // 双指针同时寻找最大和最小值 能够节省一半的循环
    public void sort2(SortableElement[] arr) {
        for (int i = 0; i < arr.length / 2; i++) {
            int minIndex = i;
            int maxIndex = i;
            for (int j = i + 1; j < arr.length - i; j++) {
                minIndex = arr[j].value < arr[minIndex].value ? j : minIndex;
                maxIndex = arr[j].value > arr[maxIndex].value ? j : maxIndex;
            }
            Tools.swap(arr, i, minIndex);
            if (maxIndex == i) {
                maxIndex = minIndex;
            } else if (maxIndex == minIndex) {
                maxIndex = i;
            }
            Tools.swap(arr, arr.length - i - 1, maxIndex);
        }
    }
}
